package com.cn.algorithm01;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/Construct-Binary-Tree-From-Preorder-And-Inorder-Traversal
 */
public class Code21_ConstructBinaryTreeFromPreorderAndInorerTraversal {
    // 创建一个二叉树节点对象
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int v) {
            val = v;
        }
    }

    public static TreeNode buildTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i], i);
        }
        return f(pre, 0, pre.length-1, in, 0, in.length-1, map);
    }

    private static TreeNode f(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {
        if (l1 > r1) {
            return null;
        }

        TreeNode head = new TreeNode(pre[l1]);
        if (l1 == r1) {
            return head;
        }

        int find = map.get(pre[l1]);

        head.left = f(pre, l1 + 1, l1 + find - l2, in , l2, find - 1, map);
        head.right = f(pre, l1 + find - l2 + 1, r1, in, find + 1, r2, map);
        return head;
    }


}
